/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */

#include "BTreeIndex.h"
#include "BTreeNode.h"
using namespace std;

#define NO_SPLIT 0
#define SPLIT 1

//#define TESTING

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;
    searchDepth = 0;
    pidCount = 0;
#ifdef TESTING
    nlInsert = 0;
#endif
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    RC rc;
    PageFile tempPf;
    //tempPf.open(indexname, mode);
    if((rc = pf.open(indexname, mode)) < 0) { return rc;}
    
    //0 is the information about the Index
    //1 should be the pid for the first node
    //because there are no deletes, 1 always exists
    if (pf.endPid() == 0) //check about the mode
    { 
            rootPid = 1;
            treeHeight = 0;
            pidCount = 1;
            BTLeafNode firstNode;
        write(buffer);
        if((rc = pf.write(0, buffer)) < 0){return rc;}
        if((rc = firstNode.write(1, pf)) < 0){return rc;}
    }
    else
    {        
        if((rc = pf.read(0, buffer)) < 0) {return rc;}
        read(buffer);
        return 0;
    }
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    RC rc;
    write(buffer);
    if((rc = pf.write(0, buffer)) < 0){return rc;}
    if((rc = pf.close()) < 0){return rc;} //check for errors
    return 0;
}
/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    RC rc;
    IndexCursor cursor;
    //set cursor to rootPid
    cursor.pid = rootPid;
    searchDepth = 0;
    if ((rc = rInsert(key,rid,cursor)) < 0 ) {return rc;}
    else {return 0;}
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @param cursor[IN] cursor.pid points to child node
 * @param cursor[OUT] cursor.pid pointing to the new node after split
 * @return error code. 0 if no error
 */
RC BTreeIndex::rInsert(int &key, const RecordId& rid, IndexCursor& cursor)
{
    //should be recursive just like locate
    //but with every *awakening* the parent function inserts if child was full.
    //must write the contents of the node before the function disappears.
    //if not zero, return the pid of the created node
    //when the original 
    
    RC rc;
    //save key and pid information since recursion changes both
    int thisKey = key;
    PageId thisPid = cursor.pid;
    

    
    if (thisPid < 0) {
        return RC_INVALID_CURSOR;
    }
    else if (searchDepth < treeHeight)
    {
        //read node contents from pf
        BTNonLeafNode node;
        if((rc = node.read(thisPid,pf)) < 0){return rc;}
        
        //retrieve pid of first elligible child
        if((rc = node.locateChildPtr(key, cursor.pid)) < 0){return rc;}
        
        //set searchDepth for recursive child
        searchDepth++;
        
        int insertReturn = rInsert(key, rid, cursor);

        //if the node below was full, the key is now the pushed up key
        if(insertReturn == SPLIT) 
        {
           
            //note, key is not thisKey
            if ((rc = node.insert(key,cursor.pid)) < 0) {                
                if (rc == RC_NODE_FULL) {
                    //insert and split
                    BTNonLeafNode sibling;
                    
                    //this will get value from insertAndSplit
                    int midKey;
                    
                    //key is midkey from recursive child
                    //cursor.pid is pid of new sibling from recursive child
                    
                    if((rc = node.insertAndSplit(key, cursor.pid, sibling, midKey)) < 0){return rc;}
                    
#ifdef TESTING
//                    cout << "SPLIT, key: " << thisKey << "pid: " << thisPid << "non leaf" << endl;
#endif //TESTING
                    //write the contents of the nodes
                    pidCount++;
                    if((rc = sibling.write(pidCount, pf)) < 0){return rc;}
  
                    if((rc = node.write(thisPid, pf)) < 0){return rc;}
                    
                    //at the root node level
                    if(searchDepth == 0)
                    {
                        BTNonLeafNode newRoot;
                        if((rc = newRoot.initializeRoot(thisPid, midKey, pidCount)) < 0){return rc;}
                        
                        pidCount++;
                        rootPid = pidCount;
                        //write the contents of the new root
                        if((rc = newRoot.write(rootPid, pf)) < 0){return rc;}
                        
                        treeHeight++;
                        //searchDepth is already 0;
                        //this is the final step so
                        //set key to original value
                        key = thisKey;
                        
#ifdef TESTING
                        /*/
                        cout << "NEW ROOT, key,pid: " << thisKey << "," << pidCount << "nonleaf " << endl;
                        cout << "and sibling pid: " << pidCount -1 << endl;
                        cout << "and original pid: " << thisPid << endl;
                         //*/
#endif //TESTING

                        return 0;
                        
                    }
                    else {
                        //set variables for recursive parent
                        cursor.pid = pidCount;
                        key = midKey;
                        searchDepth--;
                        
                        return SPLIT;
                    }
                }
                //if there were other errors
                else
                {
                    return rc; 
                }
            } 
            //if insert into node was fine
            else {
                
#ifdef TESTING
                /*/
                if (node.getKeyCount() == 127){
                    cout << "pid: " << thisPid << " node size: " << node.getKeyCount() << endl;
                    cout << "\tand newest child pid: " << cursor.pid << endl;
                    cout << "\tand the pidCount: " << pidCount << endl;
                    node.showContents();
                    
                }
                //*/
#endif //TESTING
                
#ifdef TESTING
                nlInsert++;
#endif //TESTING
                if((rc = node.write(thisPid, pf)) < 0){return rc;}
                searchDepth--;
                return 0;
            }
        }
        //if the recursive child had no splits
        else if(insertReturn == NO_SPLIT)
        {
            searchDepth--;
            return 0;
        }
    }
    
    //at the leaf level
    else if (searchDepth == treeHeight)
    { 
        
        
        //read node contents from pf
        BTLeafNode node;
        if((rc = node.read(cursor.pid,pf)) < 0){return rc;}
       // node.locate(key, cursor.eid);
        

        ///////////////////
        ///   LEAF   SPLIT 
        ///////////////////
        if ((rc = node.insert(thisKey,rid)) < 0) 
        {
            if ( rc == RC_NODE_FULL){
                BTLeafNode sibling;
                int siblingKey;
                //maybe introduce #nodes private variable
                //to keep track of insertion
                if((rc = node.insertAndSplit(thisKey, rid, sibling,siblingKey)) < 0)
                {
                    return rc;
                }
                
                pidCount++;
                if((rc = sibling.setNextNodePtr(node.getNextNodePtr())) < 0){return rc;}
                if((rc = sibling.write(pidCount, pf)) < 0){return rc;}
                
                if((rc = node.setNextNodePtr(pidCount)) < 0){return rc;}
                if((rc = node.write(cursor.pid, pf)) < 0){return rc;}
                
#ifdef TESTING
                /*/
                if(thisPid > 129){
                    cout << "SPLIT, thisPid: " << thisPid << " newPid" << pidCount << endl;
                }
                 //*/
#endif //TESTING
                
                //at the root node level
                if(searchDepth == 0)
                {                    BTNonLeafNode newRoot;
                    //pidCount is pid of the new node
                    if((rc = newRoot.initializeRoot(thisPid, siblingKey, pidCount)) < 0)
                    {
                        return rc;
                    }
                    
                    pidCount++;
                    rootPid = pidCount;
                    //write the contents of the new root
                    if((rc = newRoot.write(rootPid, pf)) < 0){return rc;}
                    
                    treeHeight++;
                    //searchDepth is already 0;
                    //this is the final step so
                    //set key to original value
                    key = thisKey;
                    
                    //decrease searchDepth for recursive parent
                    searchDepth--;
                    
                    
#ifdef TESTING
                    /*/
                    cout << "\tNEW ROOT, key,pid: " << thisKey << "," << thisPid << "tree height: " << treeHeight << " leaf" << endl;
                     //*/
#endif //TESTING

                    return 0;
                    
                }
                else {
                    //set variables for recursive parent
                    key = siblingKey;
                    cursor.pid = pidCount;
                
                    //decrease searchDepth for recursive parent
                    searchDepth--;
                    
                    //1 indicates a split was made
                    return SPLIT;
                }
            }
            //if rc is any other error
            else 
            {
                key = thisKey;
                cursor.pid = thisPid;
                return rc;
            }
        }
        else if (rc == 0)
        {
/*/
#ifdef TESTING
            int eid = -1;
            node.locate(thisKey, eid);
            cout << "key: " << thisKey << ", eid: " << eid << endl;
#endif
//*/
            if((rc = node.write(thisPid, pf)) < 0){return rc;}
            
            key = thisKey;
            cursor.pid = thisPid;
            
            //decrease searchDepth for recursive parent
            searchDepth--;
            
            return NO_SPLIT;
        }
        else 
        {
            return -1;//unknown error
        } 
    }  
    //reaches here if searchDepth > treeHeight
    //shouldn't happen
    else{
        return RC_END_OF_TREE;
    }
}
        
/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    cursor.pid = rootPid;
    searchDepth = 0;
    return rLocate(searchKey, cursor);
}
        /*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::rLocate(int searchKey, IndexCursor& cursor)
{
    RC rc;
    if (searchDepth < treeHeight)
    {
        BTNonLeafNode node;
        if((rc = node.read(cursor.pid,pf)) < 0){return rc;}
        if((rc = node.locateChildPtr(searchKey, cursor.pid)) < 0){return rc;}
        searchDepth++;
        return rLocate(searchKey, cursor);
        
    }
    else if (searchDepth == treeHeight)
    {
        BTLeafNode node;
        if((rc = node.read(cursor.pid,pf)) < 0){return rc;}
        if((rc = node.locate(searchKey, cursor.eid)) < 0){return rc;}
        searchDepth = 0;
        return 0;
    }
    else{
        return RC_END_OF_TREE;
    }
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    //will return end of tree if node is half(+1) full and eid is half(+1)+1
    //ex node just plit and has 43 keys, eid to 43 will return end
    //
    RC rc;
    if(cursor.pid < 0)
    {
        return RC_END_OF_TREE;
    }
    
    BTLeafNode node;
    if ((rc = node.read(cursor.pid,pf)) < 0){return rc;}
    if(node.readEntry(cursor.eid, key, rid) != 0){return RC_END_OF_TREE;}

    if (cursor.eid < node.getKeyCount()-1)
        //+1 because eid begins at 0
        //if there is one entry and eid is 0, then if should fail
    {
        cursor.eid++;
    }
    else
    {
        cursor.pid = node.getNextNodePtr();
        cursor.eid = 0;
        
    }
    return 0;
}


/**
 *read the buffer that stores the BTree index private information
 *1st position taking up sizeof(PageId) bytes is rootPid
 *2nd position taking up sizeof(int)bytes is treeHeight
 *3rd position taking up sizeof(int)bytes is pidCount;
 *@param pf[IN] 
 *@param buffer[OUT]
 */
void BTreeIndex::read(char * buffer)
{
    memcpy(&rootPid, buffer, sizeof(PageId)); 
    memcpy(&treeHeight, buffer + sizeof(PageId), sizeof(int));
    memcpy(&pidCount, buffer + sizeof(PageId) + sizeof(int), sizeof(int));
}

/**
 *write to the buffer with the Index informatoin
 *1st position taking up sizeof(PageId) bytes is rootPid
 *2nd position taking up sizeof(int)bytes is treeHeight
 *3rd position taking up sizeof(int)bytes is pidCount;
 *@param pf[IN] 
 *@param buffer[OUT]
 */
void BTreeIndex::write(char * buffer)
{
    memset(buffer, 0, PageFile::PAGE_SIZE);
    memcpy(buffer, &rootPid, sizeof(PageId));
    memcpy(buffer + sizeof(PageId), &treeHeight, sizeof(int));
    memcpy(buffer + sizeof(PageId) + sizeof(int), &pidCount, sizeof(int));
}

#ifdef TESTING
void BTreeIndex::showTestInfo()
{
    cout << "non leaf insertions: " << nlInsert << endl;
}
#endif
